package com.mj.listen2._02_并查集;

/**
 * Quick Union - 基于rank的优化 - 路径压缩(Path Compression)
 *
 * @author yusael
 */
public class UnionFind_QU_R_PC extends UnionFind_QU_R {

    public UnionFind_QU_R_PC(int capacity) {
        super(capacity);
    }

    /**
     * 在find时使路径上的所有节点都指向根节点，从而降低树的高度
     * 找v节点的根节点
     */
    public int find(int v) {
        if (v != parents[v]) {
            // 递归，让 v 节点指向它的父节点的根节点。
            parents[v] = find(parents[v]);
        }
        // 回溯
        return parents[v];
    }
}
